#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;

const int N = 1e6 + 5; // 定义最大节点数

// 全局变量定义
int vis[N], source[N], ans[N]; // vis: 访问次数, source: 来源安全点, ans: 距离和
vector<int> G[N];              // 邻接表存储图

int main() {
  // 输入图的节点数和边数
  int n, m;
  cin >> n >> m;

  // 构建无向图
  while (m--) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v); // 添加边 u->v
    G[v].push_back(u); // 添加边 v->u (无向图)
  }

  // 输入每个节点的类型字符串
  string s;
  cin >> s;
  s = " " + s; // 在字符串前加空格，使索引从1开始

  // 多源BFS队列：存储(当前节点, 已走距离, 来源安全点)
  queue<tuple<int, int, int>> Q;

  // 初始化：将所有安全点(S)加入队列
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'S') {             // 如果是安全点
      Q.push(make_tuple(i, 0, i)); // 加入队列：起点距离为0，来源是自己
      vis[i] = 1;                  // 标记为已访问一次
      source[i] = i;               // 记录来源安全点为自己
    }
  }

  // 多源BFS主循环 想象成一个超级源头的BFS
  while (!Q.empty()) {
    // 取出队列头部元素
    int u, d, src;
    tie(u, d, src) = Q.front();
    Q.pop();

    // 遍历当前节点的所有邻居
    for (int v : G[u]) {
      // 关键条件：节点v未被访问两次，且当前来源与之前来源不同

      // 累加到节点v的距离（d+1是从安全点到v的距离）
      if (vis[v] >= 2 || source[v] == src)
        continue;
        
      ans[v] += d + 1;
      // 增加访问次数
      vis[v]++;
      // 记录当前访问的来源安全点
      source[v] = src;
      // 将邻居节点加入队列继续BFS
      Q.push(make_tuple(v, d + 1, src));
      // Q.push({v, d + 1, src});
    }
  }

  // 输出结果：对于每个危险点(D)，输出到两个最近安全点的距离和
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'D') {        // 如果是危险点
      cout << ans[i] << endl; // 输出距离和
    }
  }

  return 0;
}